package com.fwpsl.graph.shortestpath.multisource;

import com.fwpsl.graph.Edge;
import com.fwpsl.graph.Graph;
import com.fwpsl.graph.Vertex;

import java.util.*;

/**
 * @author: 风戏fw
 * @date: 2024/4/15
 * @description: 多源最短路径抽象类
 */
public class AbstractMultiSource<T> {
    protected static final int INF = Integer.MAX_VALUE;

    /**
     * 路径节点， 包含开始顶点、结束顶点、前驱顶点、以及最短路径
     * 支持：单条最短路径和多条最短路径
     */
    class Node<T> {

        /**
         * 单条最短路径
         */
        protected static final int PATH_NODE_TYPE_SINGLE = 1;
        /**
         * 多条最短路径
         */
        protected static final int PATH_NODE_TYPE_MULTI = 2;

        Vertex<T> startVertext;
        Vertex<T> endVertext;
        Vertex<T> preVertex;
        Set<Vertex<T>> preVertexSet;
        int distance;

        /**
         * @param startVertext
         * @param endVertext
         * @param distance
         * @param type         1: 单条最短路径；2：多条最短路径
         */
        Node(Vertex<T> startVertext, Vertex<T> endVertext, int distance, int type) {
            this.startVertext = startVertext;
            this.endVertext = endVertext;
            if (type == PATH_NODE_TYPE_SINGLE) {
                this.preVertex = null;
            } else {
                this.preVertexSet = null;
            }
            this.distance = distance;
        }
    }

    /**
     * 邻接表转成邻接矩阵
     *
     * @param vertexList
     * @param type
     * @return
     */
    public Node[][] getNodeArr(List<Vertex<T>> vertexList, int type) {
        int vNum = vertexList.size();

        // nodeArr表示图的邻接矩阵。初始时，如果两个节点之间没有直接的边，我们将其值设置为无穷大。
        // 对于带权重的图，将权重直接放在相应的位置上。
        Node[][] nodeArr = new Node[vNum][vNum];
        for (int i = 0; i < vNum; i++) {
            Vertex<T> startVertex = vertexList.get(i);
            for (int j = 0; j < vNum; j++) {
                // 假设图中没有自环（即没有节点到其自身的边），如果有自环且权重为正，则需要在初始化时将nodeArr[i][i]设置为 0。
                // 如果自环的权重为其他值，则需要根据具体情况进行调整。
                nodeArr[i][j] = new Node(startVertex, vertexList.get(j), (i == j ? 0 : INF), type);
            }

            for (Edge<T> edge : startVertex.getEdges()) {
                int j = vertexList.indexOf(edge.getDestination());
                nodeArr[i][j].distance = (int) edge.getWeight();
                nodeArr[i][j].preVertexSet = new HashSet<>();
            }
        }

        return nodeArr;
    }

    /**
     * 最短路径（单条）
     *
     * @param graph
     * @return
     */
    public Node[][] singlePathList(Graph<T> graph) {
        return null;
    }

    /**
     * 最短路径（多条）
     *
     * @param graph
     * @return
     */
    public Node[][] multiPathList(Graph<T> graph) {
        return null;
    }

    /**
     * 输出单条最短路径，以及中转节点
     *
     * @param nodeArr
     */
    private void printSinglePath(Node[][] nodeArr) {
        int V = nodeArr.length;
        System.out.println("最短路径：");
        for (int i = 0; i < V; ++i) {
            for (int j = 0; j < V; ++j) {
                if (nodeArr[i][j].distance == INF) {
                    System.out.print("INF ");
                } else {
                    System.out.print(nodeArr[i][j].distance + " ");
                }
            }
            System.out.println();
        }

        System.out.println("中转节点：");
        for (int i = 0; i < V; ++i) {
            for (int j = 0; j < V; ++j) {
                if (nodeArr[i][j].distance == INF) {
                    System.out.print("INF ");
                } else {
                    System.out.print((nodeArr[i][j].preVertex == null ? "-" : nodeArr[i][j].preVertex.getData()) + " ");
                }
            }
            System.out.println();
        }
    }

    /**
     * 输出单条最短路径，以及中转节点
     *
     * @param nodeArr
     */
    private void printMultiPath(Node[][] nodeArr) {
        int V = nodeArr.length;
        System.out.println("最短路径：");
        for (int i = 0; i < V; ++i) {
            for (int j = 0; j < V; ++j) {
                if (nodeArr[i][j].distance == INF) {
                    System.out.print("INF \t");
                } else {
                    System.out.print(nodeArr[i][j].distance + "\t");
                }
            }
            System.out.println();
        }

        System.out.println("中转节点：");
        for (int i = 0; i < V; ++i) {
            for (int j = 0; j < V; ++j) {
                if (nodeArr[i][j].distance == INF) {
                    System.out.print("INF \t");
                } else {
                    String nodeStr = "-";
                    if (nodeArr[i][j].preVertexSet != null && !nodeArr[i][j].preVertexSet.isEmpty()) {
                        StringJoiner sj = new StringJoiner(",");
                        nodeArr[i][j].preVertexSet.forEach(tVertex -> sj.add(String.valueOf(((Vertex) tVertex).getData())));
                        nodeStr = sj.toString();
                    }
                    System.out.print(nodeStr + "\t");
                }
            }
            System.out.println();
        }
    }

    /**
     * 测试单条最短路径方法
     */
    public void testSinglePathList(Graph<T> graph) {
        // 单条最短路径
        Node[][] nodeArr = singlePathList(graph);
        if (nodeArr != null) {
            printSinglePath(nodeArr);
        }
    }

    /**
     * 测试多条最短路径方法
     */
    public void testMultiPathList(Graph<T> graph) {
        // 单条最短路径
        Node[][] nodeArr = multiPathList(graph);
        if (nodeArr != null) {
            printMultiPath(nodeArr);
        }
    }
}
